package com.datastructure.test.doubletoken.totalOfArray;

import java.util.ArrayList;
import java.util.Arrays;

public class TotalOfArray {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        //我再负数区 选一个则，必须在 正数区选一个，或者选两个
        for(int i=0;i<num.length;i++){
            if(num[i]>0){
                //非正数选完代表选完
                break;
            }
            if(i!=0&&num[i]==num[i-1]){
                //去重
                continue;
            }
            //两数求和\
            int start=i+1;
            int end=num.length-1;
            while(start<end){
                //先左移 因为排序原因 start 为 相对于 i 第二小值
                while(start<end&&num[i]+num[start]+num[end]>0){
                    end--;
                }
                if(start<end&&num[i]+num[start]+num[end]==0){
                    ArrayList<Integer> item=new ArrayList<Integer>();
                    item.add(num[i]);
                    item.add(num[start]);
                    item.add(num[end]);
                    result.add(item);
                    //右移去重,与前一步的剪枝相对应
                    while(start<end&&item.get(1)==num[start]){
                        start++;
                    }
                }else{
                    //右移增大整体数
                    start++;
                }
            }

        }

        return result;
    }
}
